The present invention relates generally to cryptographic devices and, more particularly, to cryptographic devices having reduced vulnerability to side-channel attack and methods for operating such devices to reduce such vulnerability. Still more particularly it relates to such devices and methods incorporated into postage metering systems employing cryptographic processes for evidencing postage payment.
Side channel attacks pose a significant threat to cryptographic systems. Such attacks involve analysis of related signals produced when an encrypted message is produced to obtain information which simplifies analysis of the cryptographic system under attack. One recently published technique of side channel attack is differential power analysis (DPA). This technique involves observation and analysis of fluctuations on the power line of a cryptographic device to determine the cryptographic secrets, i.e., the crypto keys, used by the device.
DPA attacks allow an attacker to extract secret protected information from a supposedly secure cryptographic device by measuring variations in power consumption over time, and then applying sophisticated analysis to this information. Any type of secure cryptographic device where such power variations are accessible is potentially susceptible to the attack. Such devices include smart cards, PC (PCMCIA) cards and printed circuit boards, including devices that are housed within a protected enclosure.
The attack is based on the principle that as the cryptographic processor performs its cryptographic functions, such as encryption or signing; transistors comprising the processor switch on and off, which changes the amount of current drawn from the source supplying power to the processor. The attacker can correlate the current changes with data being processed and the crypto keys ( hereinafter sometimes xe2x80x9ckeysxe2x80x9d) being used. The significance of the attack is as follows.
Secure information systems are based on an assumption that the secret information, i.e., the crypto keys, stored within a secure cryptographic device are protected against disclosure to any attacker. It is well known to use physical tamper-resistant or tamper-proof physical security to prevent such disclosure. With such physical security in effect, it has been assumed that an attacker without xe2x80x9ccribsxe2x80x9d, i.e. information of some sort to simplify the analysis, could only obtain crypto keys either by trying all the possible crypto keys associated with the algorithm being used (symmetric algorithms) or by carrying out a complex mathematical search (asymmetric algorithms). For accepted cryptographic algorithms, this search is prohibitive, e.g. obtaining a 1024 bit RSA key requires 230 years of 300 Mhz PC computing. However, the DPA attack makes this assumption false. If the cryptographic device is subject to DPA attack, then the crypto key can be obtained in a matter of days or weeks using DPA. Thus it is imperative that the security community at large find means either to defeat this attack or to at least greatly lengthen the time and expertise needed to successfully carry it out.
Many of the proposed countermeasures to the DPA attack involve the introduction of signal noise or filters on the power line, random timing and delays during cryptographic processing, and the introduction of extraneous operations. These countermeasures make the attack much more difficult by decreasing the amount of information obtained from each sampling of the power line signal. However, an attacker can overcome them by obtaining more samples of power line fluctuations and applying more sophisticated analytical techniques. Thus if a key is used sufficiently often it can be compromised by such attacks. Thus it would be advantageous to limit the amount of use of each particular key and ideally to use a different key for each message encrypted. However, this approach of substantially reducing usage creates great difficulty in the management of key distribution and is generally not useful outside of military or similar applications where the number of parties using a key is small.
One application of cryptographic processes where it is anticipated that protection against side channel attacks will be important is in postage metering systems. The vast majority of the Posts around the world require prepayment for postal services provided by the Posts. This allows the Posts to avoid the substantial time and cost associated with a post-payment system that requires processing billing data and collecting and processing remittance. Prepayment, however, necessitates that individual mailpieces carry verifiable evidence of paid postage. The traditional postage stamp is a prime example of such evidence. Postage meters which securely couple mechanical printing of postal indicia and accounting functions to assure that unpaid indicia are not printed are another well known means for evidencing postage payment. Postal revenue security in the such postage meters depends on two features: 1) physical security of the printing process, i.e., printing of postage evidence can not occur without appropriate accounting, and 2) forensic delectability, i.e., fraudulent postal indicia can be distinguished from legitimate indicia.
Coupling the printing and accounting mechanism within a secure tamper-evident enclosure provides physical security of printing. Inspection of the device normally reveals tampering. Effective forensic delectability of fraudulent postal indicia depends on non-availability of alternative mechanisms suitable for forging indicia. Before the proliferation of inexpensive, high print quality computer printers, serious attempts to generate fraudulent indicia using an alternate printing mechanism were detectable.
Today, the availability of inexpensive computer-driven printers provides opportunities for customer convenience and cost advantages for printing postage evidence. However, the use of such printers requires a new way of securing postage which was first suggested in U.S. Pat. Nos. 4,641,347, 4,641,346, 4,757,537, and 4,775,246. At that time, it was realized that the security of postage evidencing depends on the security of the information printed in the indicium, including message authentication and integrity.
U.S. Pat. Nos. 4,831,555 and 4,725,718 extended this idea to unsecured printing of postage; disclosing the necessity that at least some of the information in the indicium must appear random to a party not in possession of some secret. Such random looking information is commonly referred to as a digital token.
The basis of postal revenue security in the digital world is two new requirements: 1) security of the digital token generating process, i.e., digital tokens can not be generated without appropriate accounting, and 2) automatic delectability, i.e., fraudulent digital tokens can be detected by automatic means.
A encryption of selected data on the mailpiece with a secret key is one method for producing a digital token. The data may include postage value, date, postal code of the geographical deposit area, recipient address information, meter data, and piece count. Such data is commonly referred to as postal data. The secret key used to generate the digital token is generally held within the accounting device. A verifier, with access to a verifying key corresponding to the accounting device key, validates the digital token. Several cryptographic algorithms and protocols have been considered for this purpose. U.S. Pat. No. 4,853,961 describes critical aspects of public-key cryptography for mailing applications. See: Josxc3xa9 Pastor, CRYPTOPOST xe2x80x9cA Universal Information-Based Franking System for Automated Mail Processing, Proceedings of the Four the Advanced Technology Conference of the U.S. Postal Service, Vol. I, pp. 429-442, Nov. 1990. See also Josxc3xa9 Pastor, CRYPTOPOST xe2x80x9cA Cryptographic Application to Mail Processing, Journal of Cryptology, 3 (2), pp. 137-146, Nov. 1990.
Two methods of presenting a postal verifier with fraudulent evidence of payment are a counterfeited indicium and a copied indicium. The former is an illegitimately generated indicium that appears legitimate. The latter is a copy of a legitimate paid indicium. The subject invention addresses the prevention of counterfeit indicia by illegitimately obtaining a secret key and is not related to detection of copied indicia; which relies upon techniques such as detection of duplicate indicia.
A counterfeit indicium can be detected by verifying the digital token. Verification proves that the digital token was generated by a cryptographic algorithm with access to the secret meter key. The information printed in the indicium and access to a verifying key are sufficient for the detection of counterfeited indicia as long as the secret meter key is confidential. In a public-key system, a digital signature provides the data authentication and integrity check. In a symmetric-key system a message authentication code (MAC) provides a similar check.
Detection of counterfeiting is an integrity check. Assuming integrity of the verification software and hardware, only a compromised meter secret-key can reliably produce counterfeit indicia that passes an integrity check. This compromise could happen by violating the physical protection of the key by tampering, or by deriving the key from indicia data by cryptanalysis. Generally, tampering is detectable if the physical protection of the secure component of the postage metering system is adequate, for example following FIPS 140-1, Security Requirements for Cryptographic Modules, National Institute for Standards and Technology, Jan. 1994. Robustness against cryptanalysis depends on the difficulty of solving certain mathematical problems, for example, discrete logarithm problems or factoring a large composite number. As part of its proposed Information-Based Indicia Program (IBIP), the USPS has proposed 1024 bit RSA or 1024 bit DSS as a measure of robustness.
The IBIP is a distributed trusted system that is expected to support new methods of applying postage in addition to, and eventually in lieu of, the current approach, which typically relies on a postage meter to mechanically print indicia on mailpieces. The IBIP requires printing large, high density, two dimensional (2-D) bar codes on mailpieces. The Postal Service expects the IBIP to provide cost-effective assurance of postage payment for each mailpiece processed. The USPS has published draft specifications for the IBIP. The INFORMATION BASED INDICIA PROGRAM (IBIP) INDICIUM SPECIFICATION, dated Jun. 13, 1996, defines the proposed requirements for a new indicium that will be applied to mail being processed using the IBIP. The INFORMATION BASED INDICIA PROGRAM POSTAL SECURITY DEVICE SPECIFICATION, dated Jun. 13, 1996, defines the proposed requirements for a Postal Security Device (PSD) that will provide security services to support the creation of a new xe2x80x9cinformation basedxe2x80x9d postage postmark or indicium that will be applied to mail being processed using the IBIP. The INFORMATION BASED INDICIA PROGRAM HOST SYSTEM SPECIFICATION, dated Oct. 9, 1996, defines the proposed requirements for a host system element of the IBIP. The specifications are collectively referred to herein as the xe2x80x9cIBIP Specificationsxe2x80x9d. The IBIP includes interfacing user (customer), postal and vendor infrastructures which are the system elements of the program.
There are three information security objectives critical for postage evidencing: authentication, wherein a Post can read a payment message printed on a mailpiece and identify the postage accounting device responsible for the message; data Integrity, wherein the Post can detect any alteration of the payment message; and evidence of fraud, wherein the Post can detect evidence of fraud, such as a mailpiece with a counterfeited indicium or mailpieces with identical indicia.
In order to achieve authentication, the payment message must include an unique postage accounting device identification number and a message identification number, for example, a serial piece count or ascending register. The integrity of the payment itself requires inclusion of the postage amount. These elements, collectively referred to as postal or security data, represent a minimal set. Depending on the verification strategy additional elements, including delivery address information, may be included. An indicium should, at a minimum, contain: 1) the security data, and 2) the digital token produced by a encryption of the security data. Cryptographic authentication proves integrity of these elements.
Presently, there are two postage metering types: closed systems and open systems. In a closed system, the system functionality is solely dedicated to metering activity. Examples of closed system metering devices include conventional digital and analog (mechanical and electronic) postage meters wherein a dedicated printer is securely coupled to a metering or accounting function. In a closed system, since the printer is securely coupled and dedicated to the meter, printing evidence of postage cannot take place without accounting for the evidence of postage. In an open system, the printer is not dedicated to the metering activity, freeing system functionality for multiple and diverse uses in addition to the metering activity. Examples of open system metering devices include personal computer (PC) based devices with single/multi-tasking operating systems, multi-user applications and digital printers. An open system metering device is a postage evidencing device with a non-dedicated printer that is not securely coupled to a secure accounting module. Open system indicia printed by the non-dedicated printer are made secure by including addressee information in the encrypted evidence of postage printed on the mailpiece for subsequent verification.
Conventional closed system mechanical and electronic postage meters have heretofore secured the link between printing and accounting. The integrity of the physical meter box has been monitored by periodic inspections of the meters. Digital printing postage meters, which are closed system postage meters, typically include a digital printer coupled to a metering (accounting) device, which is referred to herein as a postal security device (PSD). Digital printing postage meters have removed the need for physical inspection by cryptographically securing the link between the accounting and printing mechanisms. In essence, new digital printing postage meters create a secure point to point communication link between the accounting unit and printhead. That is an indicium printed without accounting for postage will be detected. See, for example, U.S. Pat. No. 4,802,218, issued to Christopher B. Wright et al and now assigned to the assignee of the present invention. An example of a digital printing postage meter with secure printhead communication is the Personal Post Officexe2x80x9d manufactured by Pitney Bowes Inc. of Stamford, Connecticut. An example of a digital printing postage meter in a secure housing is the PostPerfectxe2x80x9d also manufactured by Pitney Bowes Inc.
It will be apparent from the above discussion that protection of secret meter keys is critical to the success of new meter technologies such as the IBIP. Compromise of a meter secret key can allow the generation of counterfeit indicia which cannot be detected by cryptographic verification, while the reduced need for physical inspection of the meters may increase opportunities for side-channel attacks such as DPA.
Thus it is an object of the subject invention to provide cryptographic devices and methods for operation of such devices which reduce the vulnerability to side-channel attacks, particularly DPA.
The above object is achieved and the disadvantages of the prior art are overcome in accordance with the subject invention by means of a cryptographic device and a method for operating such a device which include:
a) storing a key e and an encryption function E(x,y), where E(x,y) is an encryption of an arbitrary message x with an arbitrary key y in the device;
b) storing a first, resistant function F1(y,t) and a second function F2(x,t), where t is an arbitrary integer and F2(E(x, F1(y,t)), t)=E(x,y) in the device; and then controlling the device to
c) input a message m for encryption;
d) select a random number r;
e) generate a temporary key F1(e,r);
f) generate E(m, F1(e,r));
g) generate F2(E(m, F1(e,r)), r)=E(m,e) as an encryption c of the message m with the key e; and
h) output the encryption c.
Thus signals generated by said device which are susceptible to side-channel attack will vary with the random number r thus reducing the vulnerability of the key e to side channel analysis.
In accordance with one aspect of the subject invention, where n is a secret number equal to p times q, where p and q are secret prime numbers, and where xcfx86(n) is the number of positive integers less than or equal to n that are relatively prime to n:
a) the encryption function E(x,y) equals xy mod(n);
b) the first function F1(y,t) equals (y)(1/t mod(xcfx86(n))); and
c) the second function F2(x,t) equals xt mod(n); with the result that
d) F2(E(m, F1(e,r)), r)=(me/r mod(n))r mod(n), where the exponent e/r is taken to be (e)(1/r mod(xcfx86(n))), equals me mod(n), as the encryption c of the message m; whereby a recipient of the encryption c can recover the message m as cd mod(n), where (e)(d)=1 mod(xcfx86(n)).
In accordance with another aspect of the subject invention the message m includes postal data and the encryption c is incorporated into a postal indicium.
In accordance with another aspect of the subject invention values for r are generated by a random number generator.
In accordance with another aspect of the subject invention values for r and (1/r mod(xcfx86(n))) are selected from a table of predetermined values.
In accordance with still another aspect of the subject invention, where the computational burden is distributed between the message originator and message recipient, the device is operated to:
a) store a key e and an encryption function E(x,y), where E(x,y) is an encryption of an arbitrary message x with an arbitrary key y in the device;
b) store a first, resistant function F1(y,t) and a second function F2(x,t), where t is an arbitrary integer and F2(E(x, F1(y,t)), t)=E(x,y) in the device; and then to
c) input a message m for encryption;
d) select a random number r;
e) generate a temporary key F1(e,r);
f) generate E(m, F1(e,r)); and the to
g) output E(m, F1(e,r)), the message recipient being provided with the random number r. The message recipient can generate F2(E(m, F1(e,r)), r)=E(m,e) as an encryption c of said message m with said key e, and then decrypt said encryption c.